package org.atovio.structure.tree;

/**
 * 二叉树类，采用二叉链表
 *
 * @author AtoVio, Winter Yuan
 * @version 1.0
 */
public class BinaryTree<T> {

    // 根结点
    private BinaryNode<T> root;
    // 以序列构造二叉树时用到的变量
    private int i = 0;
    // toString方法用到的字符串
    private String treeString;

    /**
     * 构造空树
     */
    public BinaryTree() {
        this.root = null;
    }

    /**
     * 根据标明空子树的先序序列来构造二叉树
     *
     * @param preList 标明空子树的先序序列
     */
    public BinaryTree(T[] preList) {
        root = create(preList);
    }

    /**
     * 根据 从i开始的标明空子树的先序序列 来构造以preList[i]为根的子树。
     *
     * @param preList 标明空子树的先序序列
     * @return 根结点
     */
    public BinaryNode<T> create(T[] preList) {
        BinaryNode<T> p = null;
        if (i < preList.length) {
            T elem = preList[i++];
            if (elem != null) {
                // 先构造父结点
                p = new BinaryNode<>(elem);
                // 构造左子树
                p.left = create(preList);
                // 构造右子树
                p.right = create(preList);
            }
        }
        return p;
    }

    public BinaryNode<T> getRoot() {
        return this.root;
    }

    public boolean isEmpty() {
        return this.root == null;
    }

    /**
     * 根结点插入
     *
     * @param value 数据
     */
    public void insert(T value) {
        if (value != null)
            root = new BinaryNode<>(value, root, null);
    }

    /**
     * 指定待结点为p结点的左/右孩子
     * @param p     待插入位置
     * @param left  待插入结点是否为p的左孩子。
     * @param value 数据
     */
    public void insert(BinaryNode<T> p, boolean left, T value) {
        if (p == null || value == null)
            return;
        // 插入为p的左孩子
        if (left) {
            p.left = new BinaryNode<>(value, p.left, null);
            return;
        }
        // 插入为p的右孩子
        p.right = new BinaryNode<>(value, null, p.right);
    }

    /**
     * 删除指定结点的左/右子树
     * @param p    指定的结点
     * @param left 是否删除左子树
     */
    public void remove(BinaryNode<T> p, boolean left) {
        if (p != null) {
            if (left)
                p.left = null;
            else
                p.right = null;
        }
    }

    public void clear() {
        root = null;
    }

    /**
     * 先序遍历整棵二叉树
     */
    public void preOrder() {
        preOrder(root);
        System.out.println();
    }

    /**
     * 指定结点的先序遍历
     * @param p 遍历开始的结点
     */
    public void preOrder(BinaryNode<T> p) {
        if (p != null) {
            System.out.print(p + " ");
            preOrder(p.left);
            preOrder(p.right);
        }
    }

    /**
     * 中序遍历整棵二叉树
     */
    public void inOrder() {
        inOrder(root);
        System.out.println();
    }

    /**
     * 指定结点的中序遍历
     * @param p 遍历开始的结点
     */
    public void inOrder(BinaryNode<T> p) {
        if (p != null) {
            inOrder(p.left);
            System.out.print(p + " ");
            inOrder(p.right);
        }
    }

    /**
     * 后序遍历二叉树
     */
    public void postOrder() {
        postOrder(root);
        System.out.println();
    }

    /**
     * 指定结点的后序遍历
     * @param p 遍历开始的结点
     */
    public void postOrder(BinaryNode<T> p) {
        if (p != null) {
            postOrder(p.left);
            postOrder(p.right);
            System.out.print(p + " ");
        }
    }

    /**
     * 先序遍历的toString方法
     */
    @Override
    public String toString() {
        return toString(root);
    }

    /**
     * toString方法的实现
     */
    private String toString(BinaryNode<T> p) {
        String str = p + " ";
        if (p != null) {
            str += toString(p.left);
            str += toString(p.right);
        }
        return str;
    }
}
